#include<iostream>
#include<string>
#include<algorithm>

using namespace std;
const int SIZE = 31;
inline bool rematch(char a, char b)
{
    return a == b || a == '.' || b == '.' ? true : false;
}
inline bool isMatch(string s, string p)
{
    bool res[SIZE][SIZE]{0};
    res[0][0] = true;
    for(int i = -1;i<(int)s.length();++i)
    {
        for(int j = 0;j<p.length();++j)
        {
            if(p[j] == '*')
            {
                res[i+1][j+1] =  res[i+1][j-1] || ( i>=0 &&rematch(s[i],p[j-1])? res[i][j+1] : false);
            }
            else
            {
                res[i+1][j+1] = (i>=0 && rematch(s[i],p[j]))? res[i][j] : false;
            }
        }
    }
    return res[s.length()][p.length()];
}

bool isMatch(string s, string p)
{
    bool res[SIZE][SIZE]{0};
    res[0][0] = true;
    for(int i = -1;i<(int)s.length();++i)
    {
        for(int j = 0;j<p.length();++j)
        {
            if(p[j] == '*')
            {
                res[i+1][j+1] =  res[i+1][j-1] || ( i>=0 &&rematch(s[i],p[j-1])? res[i][j+1] : false);
            }
            else
            {
                res[i+1][j+1] = (i>=0 && rematch(s[i],p[j]))? res[i][j] : false;
            }
        }
    }
    return res[s.length()][p.length()];
}

int main(int argc, char const *argv[])
{
    string s="ab",p=".*";
    if(isMatch(s,p))  cout<<"isMatch!\n"; 
    else cout<<"notMatch!\n";
    
    return 0;
}
